package com.duoduo.栈和队列;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @program: algorithm
 * @description: 每日温度739
 * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 *
 * 示例 1:
 *
 * 输入: temperatures = [73,74,75,71,69,72,76,73]
 * 输出: [1,1,4,2,1,1,0,0]
 * 示例 2:
 *
 * 输入: temperatures = [30,40,50,60]
 * 输出: [1,1,1,0]
 *
 * @author: chaidl  ！
 * @create: 2022-05-18 23:09
 */
public class 每日温度739 {
	//使用单调栈的解决方式
	public int[] dailyTemperatures(int[] temperatures) {
		int length=temperatures.length;
		Deque<Integer> stack=new LinkedList<>();
		int[] result=new int[length];
		for (int i = 0; i < length; i++) {
			//如果栈不为空，并且当前元素比栈顶元素大，那么要将此数据压栈，栈顶出栈
			while (!stack.isEmpty() && temperatures[i]>temperatures[stack.peek()]){
				int index=stack.pop();
				result[index]=i-index;
			}
			stack.push(i);
		}
		return result;
	}
}
